package algorithm.tree;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 非递归遍历二叉树
 * @author shenenlu 2021年05月13日 下午17:22:09
 */
public class AccessTreeNotRecursively {

    static class Node{
        int value;

        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    static class AccessTreeHelper{
        List<Integer> result;

        Stack<NodeHelper> trace;


        public AccessTreeHelper() {
            result = new ArrayList<>();
            trace = new Stack<>();
        }

        static class NodeHelper{
            Node node;
            boolean leftVisited;
            boolean rightVisited;

            public NodeHelper(Node node) {
                this.node = node;
                leftVisited = false;
                rightVisited = false;
                if( node.left == null ){
                    leftVisited = true;
                }
                if( node.right == null ){
                    rightVisited = true;
                }
            }

            public boolean isVisited(){
                return leftVisited && rightVisited;
            }
        }

        boolean checkAllVisited(List<NodeHelper> allNodes){
            for( NodeHelper nodeHelper : allNodes){
                if( !nodeHelper.isVisited() ){
                    return false;
                }
            }
            return true;
        }

        void accessTree(Node root){
            if( root == null){
                return;
            }
            NodeHelper currNode = new NodeHelper(root);
            trace.add(currNode);
            result.add(currNode.node.value);

            while (  !checkAllVisited(trace) ){
                if( currNode.node.left != null && !currNode.leftVisited ){
                    currNode.leftVisited = true;
                    trace.push(currNode);
                    result.add(currNode.node.value);
                    //访问左子节点
                    currNode = new NodeHelper(currNode.node.left);
                } else if( currNode.node.right != null && !currNode.rightVisited){
                    currNode.rightVisited = true;
                    trace.push(currNode);
                    result.add(currNode.node.value);
                    //访问右子节点
                    currNode = new NodeHelper(currNode.node.right);
                }else{
                    trace.pop();
                    currNode = trace.peek();
                }
            }
        }
    }


    /**
     *     1
     *     /\
     *   2   3
     *   /\  /
     *  4 5 6
     *    \
     *     7
     * @param args
     */
    public static void main(String[] args) {
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        root.left = node2;
        root.right = node3;

        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node5.right = node7;

        AccessTreeHelper accessTreeHelper = new AccessTreeHelper();
        accessTreeHelper.accessTree(root);
        System.out.println(accessTreeHelper.result);
    }

}
